﻿/**
 * 合并任意多边形，将两个相交的多边形（凸凹）合并成一个新的多边形，
 * 
 * 目前的bug：
 *      1、任意两个多边形（a，b），如果相交，则交点不能是a或者b的任何一个顶点，否则崩溃（尚未解决）
 *      
 * 请大家编辑多边形的时候避免出现bug的情况
 */

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Node
{
    //data
    /// <summary>
    /// 是否是交点
    /// </summary>
    public bool mInsPoint;
    /// <summary>
    /// 是否已经遍历过
    /// </summary>
    public bool mPassPoint;
    /// <summary>
    /// 是否为出点，true为出点，false为进点
    /// </summary>
    public bool mIsOutPoint;
    /// <summary>
    /// 是否是主多边形上的点
    /// </summary>
    public bool isMainPoint;
    /// <summary>
    /// 多边形指向与之相交多边形的指针
    /// </summary>
    public Node other;

    public Vector3 Pos;
    public Node(Vector3 tPos, bool tIsMainPoint, bool tInsPoint)
    {
        Pos = tPos;
        mInsPoint = tInsPoint;
        isMainPoint = tIsMainPoint;
        mPassPoint = false;
        mIsOutPoint = false;

        last = null;
        next = null;
        other = null;
    }

    private Node last;
    public Node next;
    public void AddNode(Node tNode)
    {
        if (last == null)
            return;
        last.next = tNode;
        last = tNode;
    }

    public static Node CreateLinkedList(Vector3 tPos, bool tIsMainPoint, bool tInsPoint)
    {
        Node node = new Node(tPos, tIsMainPoint, tInsPoint);
        node.last = node;
        return node;
    }
}

public class MergerPolygon
{
    /**
     * 合并两个多边形(Weiler-Athenton算法)
     * @param polygon
     * @return 
     * null--两个多边形不相交，合并前后两个多边形不变
     * Polygon--一个新的多边形
     */
    public static List<List<Vector3>> Union(List<Vector3> mBounds1, List<Vector3> mBounds2)
    {
        //所有顶点和交点
        Node nodelist0 = null;//主多边形
        Node nodelist1 = null;//合并多边形
        //初始化
        for (int i = 0; i < mBounds1.Count; i++)
        {
            if (nodelist0 == null)
                nodelist0 = Node.CreateLinkedList(mBounds1[i], true, false);
            else
                nodelist0.AddNode(new Node(mBounds1[i], true, false));
        }
        for (int i = 0; i < mBounds2.Count; i++)
        {
            if (nodelist1 == null)
                nodelist1 = Node.CreateLinkedList(mBounds2[i], false, false);
            else
                nodelist1.AddNode(new Node(mBounds2[i], false, false));
        }

        //插入交点
        int insCnt = IntersectPoint(nodelist0, nodelist1);

        //生成多边形
        if (insCnt > 0)
        {
            //顺时针序
            return LinkToPolygon(nodelist0, nodelist1);
        }
        else
        {
            return null;
        }
    }

    /**
     * 生成多边形，顺时针序； 生成的内部孔洞多边形为逆时针序
     * @param cv0
     * @param cv1
     * @return 合并后的结果多边形数组(可能有多个多边形)
     */
    private static List<List<Vector3>> LinkToPolygon(Node cv0, Node cv1)
    {
        //保存合并后的多边形数组
        List<List<Vector3>> rtV = new List<List<Vector3>>();

        //1. 选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．
        Node indexNode = cv0;
        while (indexNode != null)
        {
            Node node = indexNode;
            if (node.mInsPoint == true && node.mPassPoint == false)
            {
                List<Vector3> rcNodes = new List<Vector3>();
                while (node != null)
                {
                    node.mPassPoint = true;
                    // 如果是交点
                    if (node.mInsPoint == true)
                    {
                        node.other.mPassPoint = true;

                        if (node.mIsOutPoint == false)
                        {
                            //该交点为进点（跟踪裁剪多边形边界）
                            if (node.isMainPoint == true)
                            {
                                //当前点在主多边形中，切换到裁剪多边形中
                                node = node.other;
                            }
                        }
                        else
                        {
                            //该交点为出点（跟踪主多边形边界）
                            if (node.isMainPoint == false)
                            {
                                //当前点在裁剪多边形中，//切换到主多边形中
                                node = node.other;
                            }
                        }
                    }

                    // 如果是多边形顶点，将其输出到结果多边形顶点表中
                    rcNodes.Add(node.Pos);

                    if (node.next == null)
                    {    
                        //末尾点返回到开始点
                        if (node.isMainPoint)
                        {
                            node = cv0;
                        }
                        else
                        {
                            node = cv1;
                        }
                    }
                    else
                    {
                        node = node.next;
                    }

                    //与首点相同，生成一个多边形
                    if (node.Pos.Equals(rcNodes[0])) break;
                }
                //提取
                rtV.Add(rcNodes);
            }

            indexNode = indexNode.next;
        }
        return rtV;
    }

    /**
     * 生成交点，并按顺时针序插入到顶点表中
     * @param cv0 （in/out）主多边形顶点表，并返回插入交点后的顶点表
     * @param cv1 （in/out）合并多边形顶点表，并返回插入交点后的顶点表
     * @return 交点数
     */
    private static int IntersectPoint(Node cv0, Node cv1)
    {
        int insCnt = 0;        //交点数

        Node startNode0 = cv0;
        Node startNode1;
        Line line0;
        Line line1;
        Vector3 ins;
        bool hasIns;

        while (startNode0 != null)
        {
            //主多边形
            if (startNode0.next == null)
            {  //最后一个点，跟首点相连
                line0 = new Line(startNode0.Pos, cv0.Pos);
            }
            else
            {
                line0 = new Line(startNode0.Pos, startNode0.next.Pos);
            }

            startNode1 = cv1;
            hasIns = false;

            while (startNode1 != null)
            {
                //合并多边形
                if (startNode1.next == null)
                {
                    line1 = new Line(startNode1.Pos, cv1.Pos);
                }
                else
                {
                    line1 = new Line(startNode1.Pos, startNode1.next.Pos);
                }

                ins = new Vector3();    //接受返回的交点

                //有交点
                if (Line.CheckIntersection(line0, line1, ref ins))
                {
                    //忽略交点已在顶点列表中的
                    if (GetNodeIndex(cv0, ins) == -1)
                    {
                        insCnt++;

                        // 插入交点
                        Node node0 = new Node(ins, true, true);
                        Node node1 = new Node(ins, false, true);
                        //双向引用
                        node0.other = node1;
                        node1.other = node0;
                        //插入
                        node0.next = startNode0.next;
                        startNode0.next = node0;
                        node1.next = startNode1.next;
                        startNode1.next = node1;

                        //出点
                        // 判断点是否在线的左边（注意unity坐标系为左手坐标系）
                        if (Vector3.Cross(line1.mPoint1 - line0.mPoint1, line0.mPoint2 - line0.mPoint1).y > 0)
                        {
                            node0.mIsOutPoint = true;
                            node1.mIsOutPoint = true;
                        }

                        hasIns = true;
                        break;
                    }
                }
                startNode1 = startNode1.next;
            }
            //如果没有交点继续处理下一个边，否则重新处理该点与插入的交点所形成的线段
            if (hasIns == false)
            {
                startNode0 = startNode0.next;
            }
        }
        return insCnt;
    }

    /**
     * 取得节点的索引(合并多边形用)
     * @param cv
     * @param node
     * @return 
     */
    private static int GetNodeIndex(Node cv, Vector3 nodePos)
    {
        Node temp = cv;
        int index = -1;
        while (temp != null)
        {
            index++;
            if (temp.Pos == nodePos)
            {
                return index;
            }
            else
            {
                temp = temp.next;
            }
        }
        return -1;
    }
}
